# !/usr/bin/env python3
from typing import List


class Solution:
    def mySqrt(self, num: int) -> int:
        if (num == 1):
            return 1;
        left = 0
        right = num
        while right - left>1:
            mid = left + (right - left)//2
            if mid*mid > num:
                right = mid
            else:
                left = mid
        return left
    
    # 最简单的方式
    def mySqrt(self,num: int) -> int:
        return int(num**0.5)

def main():
    solu = Solution()
    nums = [-1,0,3,5,9,12]
    target = 9
    print(solu.search(nums, target))


if __name__ == '__main__':
    main()